SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Implicit data structure</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Implicit data structure</span></span>

</h1>

</header>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, an <b>implicit data structure</b> or <b>space-efficient data structure</b> is a <a href="Data_structure" title="Data structure">data structure</a> that stores very little information other than the main or required data: a data structure that requires low <a href="Overhead_(computing)" title="Overhead (computing)">overhead</a>. They are called "implicit" because the position of the elements carries meaning and relationship between elements; this is contrasted with the use of <a href="Pointer_(computer_science)" class="mw-redirect" title="Pointer (computer science)">pointers</a> to give an <i>explicit</i> relationship between elements. Definitions of "low overhead" vary, but generally means constant overhead; in <a href="Big_O_notation" title="Big O notation">big O notation</a>, <i>O</i>(1) overhead. A less restrictive definition is a <a href="Succinct_data_structure" title="Succinct data structure">succinct data structure</a>, which allows greater overhead.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>An implicit data structure is one with constant <span class="texhtml"><i>O</i>(1)</span> space overhead (above the <a href="Information-theoretic" class="mw-redirect" title="Information-theoretic">information-theoretic</a> lower bound).

</p><p>Historically, <a href="#CITEREFMunroSuwanda1980">Munro & Suwanda (1980)</a> defined an implicit data structure (and algorithms acting on one) as one "in which structural information is implicit in the way data are stored, rather than explicit in pointers." They are somewhat vague in the definition, defining it most strictly as a single array, with only the size retained (a single number of overhead),<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> or more loosely as a data structure with constant overhead (<span class="texhtml"><i>O</i>(1)</span>).<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> This latter definition is today more standard, and the still-looser notion of a data structure with non-constant but small <span class="texhtml"><i>o</i>(<i>n</i>)</span> overhead is today known as a <a href="Succinct_data_structure" title="Succinct data structure">succinct data structure</a>, as defined by <a href="#CITEREFJacobson1988">Jacobson (1988)</a>; it was referred to as <b>semi-implicit</b> by <a href="#CITEREFMunroSuwanda1980">Munro & Suwanda (1980)</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>A fundamental distinction is between <i>static</i> data structures (read-only) and <a href="Dynamization" title="Dynamization"><i>dynamic</i> data structures</a> (which can be modified). Simple implicit data structures, such as representing a sorted list as an array, may be very efficient as a static data structure, but inefficient as a dynamic data structure, due to modification operations (such as insertion in the case of a sorted list) being inefficient.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>A trivial example of an implicit data structure is an <i><a href="Array_data_structure" class="mw-redirect" title="Array data structure">array data structure</a></i>, which is an implicit data structure for a <a href="List_(abstract_data_type)" title="List (abstract data type)">list</a>, and requires only the constant overhead of the length; unlike a <a href="Linked_list" title="Linked list">linked list</a>, which has a pointer associated with each data element, which <i>explicitly</i> gives the relationship from one element to the next. Similarly, a <i><a href="Null-terminated_string" title="Null-terminated string">null-terminated string</a></i> is an implicit data structure for a <a href="String_(computer_science)" title="String (computer science)">string</a> (list of characters). These are considered very simple because they are static data structures (read-only), and only admit the simple operation of iteration over the elements.

</p><p>Similarly simple is representing a <a href="Multi-dimensional_array" class="mw-redirect" title="Multi-dimensional array">multi-dimensional array</a> as a single 1-dimensional array, together with its dimensions. For example, representing an <i>m</i> × <i>n</i> array as a single list of length <i>m·n</i>, together with the numbers <i>m</i> and <i>n</i> (instead of as a 1-dimensional array of pointers to each 1-dimensional subarray). The elements need not be of the same type, and a <a href="Table_(information)" title="Table (information)">table</a> of data (a list of <a href="Record_(computer_science)" title="Record (computer science)">records</a>) may similarly be represented implicitly as a flat (1-dimensional) list, together with the length of each <a href="Field_(computer_science)" title="Field (computer science)">field</a>, so long as each field has uniform size (so a single size can be used per field, not per record).

</p><p>A less trivial example is representing a sorted list by a <i><a href="Sorted_array" title="Sorted array">sorted array</a></i>, which allows search in logarithmic time by <a href="Binary_search" title="Binary search">binary search</a>. Contrast with a <a href="Search_tree" title="Search tree">search tree</a>, specifically a <a href="Binary_search_tree" title="Binary search tree">binary search tree</a>, which also allows logarithmic-time search, but requires pointers. A sorted array is only efficient as a static data structure, as modifying the list is slow – unlike a binary search tree – but does not require the space overhead of a tree.

</p><p>An important example of an implicit data structure is representing a <a href="Perfect_binary_tree" class="mw-redirect" title="Perfect binary tree">perfect binary tree</a> as a list, in increasing order of depth, so root, first left child, first right child, first left child of first left child, etc. Such a tree occurs notably for an <a href="Ancestry_chart" class="mw-redirect" title="Ancestry chart">ancestry chart</a> to a given depth, and the implicit representation is known as an <i><a href="Ahnentafel" title="Ahnentafel">Ahnentafel</a></i> (ancestor table).

</p><p>This can be generalized to a <a href="Complete_binary_tree" class="mw-redirect" title="Complete binary tree">complete binary tree</a> (where the last level may be incomplete), which yields the best-known example of an implicit data structure, namely the <i><a href="Binary_heap" title="Binary heap">binary heap</a></i>, which is an implicit data structure for a <a href="Priority_queue" title="Priority queue">priority queue</a>. This is more sophisticated than earlier examples because it allows multiple operations, and is an efficient <i>dynamic</i> data structure (it allows efficient modification of the data): not only <b>top</b>, but also <b>insert</b> and <b>pop</b>.

</p><p>More sophisticated implicit data structures include the <a href="Beap" title="Beap">beap</a> (bi-parental heap).

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>The trivial examples of lists or tables of values date to prehistory, while historically non-trivial implicit data structures date at least to the Ahnentafel, which was introduced by <a href="Micha%C3%ABl_Eytzinger" title="Michaël Eytzinger">Michaël Eytzinger</a> in 1590 for use in genealogy. In formal computer science, the first implicit data structure is generally considered to be the sorted list, used for binary search, which was introduced by <a href="John_Mauchly" title="John Mauchly">John Mauchly</a> in 1946, in the <a href="Moore_School_Lectures" title="Moore School Lectures">Moore School Lectures</a>, the first ever set of lectures regarding any computer-related topic.<sup id="cite_ref-FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"_4-0" class="reference"><a href="#cite_note-FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-FranceschiniMunro2006_5-0" class="reference"><a href="#cite_note-FranceschiniMunro2006-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> The binary heap was introduced in <a href="#CITEREFWilliams1964">Williams (1964)</a> to implement the <a href="Heapsort" title="Heapsort">heapsort</a>.<sup id="cite_ref-FranceschiniMunro2006_5-1" class="reference"><a href="#cite_note-FranceschiniMunro2006-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> The notion of an implicit data structure was formalized in <a href="#CITEREFMunroSuwanda1980">Munro & Suwanda (1980)</a>, as part of introducing and analyzing the <a href="Beap" title="Beap">beap</a>.<sup id="cite_ref-FranceschiniMunro2006_5-2" class="reference"><a href="#cite_note-FranceschiniMunro2006-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">"Thus, only a simple array is needed for the data.", p. 236; "We will draw no formal distinction between a pointer and an integer (index) in the range <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,N]}</annotation>

</semantics>

</math></span><img src="./703d57dca548a7f9d927247c2a27b67666aebdd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.554ex; height:2.843ex;" alt="{\displaystyle [0,N]}" loading="lazy"></span>. A data structure is then implicit, if the only such integer which need be retained is <i>N</i> itself.", p. 238</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">"... one might prefer to permit a constant number of pointers to be retained and still designate the structure as implicit.", p. 238</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">"We will also suggest two structures which might be described as “semi-implicit,” in that a variable, but <i>o</i>(<i>N</i>), number of pointers (indices) is kept.", p. 238</span>

</li>

<li id="cite_note-FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"_4-0">^</a></b></span> <span class="reference-text"><a href="#CITEREFKnuth1998">Knuth 1998</a>, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFranceschiniMunro2006" class="citation conference cs1">Franceschini, Gianni; <a href="Ian_Munro_(computer_scientist)" title="Ian Munro (computer scientist)">Munro, J. Ian</a> (2006). <i>Implicit dictionaries with </i>O<i>(1) modifications per update and fast search</i>. Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms. Miami, FL, United States. pp. <span class="nowrap">404–</span>413. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1109557.1109603">10.1145/1109557.1109603</a>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFJacobson1988" class="citation thesis cs1">Jacobson, G. J (1988). <i>Succinct static data structures</i> (Ph.D.). Pittsburgh, PA: Carnegie Mellon University.</cite></li>

<li><cite id="CITEREFKnuth1998" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1998). <i>Sorting and searching</i>. <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-201-89685-5</bdi>.</cite></li>

<li><cite id="CITEREFMunroSuwanda1980" class="citation journal cs1"><a href="Ian_Munro_(computer_scientist)" title="Ian Munro (computer scientist)">Munro, J.Ian</a>; Suwanda, Hendra (October 1980). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2880%2990037-9">"Implicit data structures for fast search and update"</a>. <i><a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>. <b>21</b> (2): <span class="nowrap">236–</span>250. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2880%2990037-9">10.1016/0022-0000(80)90037-9</a></span>.</cite></li>

<li><cite id="CITEREFWilliams1964" class="citation journal cs1">Williams, J. W. J. (June 1964). "Algorithm 232 - Heapsort". <i>Communications of the ACM</i>. <b>7</b> (6): <span class="nowrap">347–</span>348. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F512274.512284">10.1145/512274.512284</a>.</cite></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<p>See publications of <a rel="nofollow" class="external text" href="https://web.archive.org/web/20051217162328/http://photon.poly.edu/~hbr/">Hervé Brönnimann</a>, <a href="J._Ian_Munro" class="mw-redirect" title="J. Ian Munro">J. Ian Munro</a>, and <a rel="nofollow" class="external text" href="http://www.cs.purdue.edu/people/gnf">Greg Frederickson</a>.

</p></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-01-12" href="https://en.wikipedia.org/wiki/?title=Implicit_data_structure&oldid=1268988798">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>